package 数据结构考纲.排序;

import java.util.Arrays;

public class Sort {
    //插入排序
    public static void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int t = nums[i], j = i - 1;
            while (j >= 0 && nums[j] > t) {
                nums[j + 1] = nums[j];
                j -= 1;
            }
            nums[j + 1] = t; //j此时指向第一个小于t的元素，也可能是-1，而待插入位置为第一个大于j的元素的位置
        }
    }

    //折半插入
    public static void bInsertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            //找到第一个比a[i]小的元素，即二分结束后r的位置
            int t = nums[i];
            int l = 0, r = i - 1, mid;
            while (l <= r) {
                mid = (l + r) / 2;
                if (nums[mid] > t)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            for (int k = i; k > l; k--) {   //将[j,i-1]间的元素后移一位，将a[i] 放在a[j]处
                nums[k] = nums[k - 1];
            }
            nums[l] = t;
        }
    }

    //希尔排序
    public static void shellSort(int[] nums) {

        for (int dk = nums.length / 2; dk >= 1; dk /= 2) {  //希尔排序的增量（子表每个元素的间隔）
            //对各个内的元素进行插入排序
            for (int i = dk; i < nums.length; i++) {
                int t = nums[i], j = i - dk;
                while (j >= 0 && nums[j] > t) {
                    nums[j + dk] = nums[j];
                    j -= dk;
                }
                nums[j + dk] = t; //j此时指向第一个小于t的元素，也可能是-1，而待插入位置为第一个大于j的元素的位置
            }
        }
    }

    //冒泡排序
    public static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    flag = true;
                    int t = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = t;
                }
            }
            if (!flag)
                return;
        }
    }

    //快速排序
    public static void quickSort(int[] nums) {
        quickSortTool(nums, 0, nums.length - 1);
    }

    private static void quickSortTool(int[] nums, int l, int r) {
        if (l < r) {
            int mid = quickSortPartition(nums, l, r);
            quickSortTool(nums, l, mid - 1);
            quickSortTool(nums, mid + 1, r);
        }
    }

    private static int quickSortPartition(int[] nums, int l, int r) {
        //第一个作为枢纽
        int t = nums[l];
        while (l < r) {
            //从右开始,找到右边比其小的
            while (r > l && nums[r] >= t) r--;
            nums[l] = nums[r];
            //找到左边比其大的
            while (l < r && nums[l] <= t) l++;
            nums[r] = nums[l];
        }
        nums[l] = t;
        return l;
    }

    //简单选择排序
    public static void selectSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int min_i = i;
            for (int j = min_i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min_i])
                    min_i = j;
            }
            int t = nums[min_i];
            nums[min_i] = nums[i];
            nums[i] = t;
        }
    }

    //大根堆（升序）
    public static void heapSort(int[] nums) {
        buildMaxHeap(nums);
        //将堆顶元素交换到堆尾部
        for (int i = 0; i < nums.length - 1; i++) {
            swap(nums, 0, nums.length - 1 - i);
            adjustMaxHeap(nums, 0, nums.length - 1 - i);
        }

    }

    //建立大根堆
    private static void buildMaxHeap(int[] nums) {
        //下标从0开始，最后一个节点的编号为len-1，其双亲的父母为 (len-2)/2
        int c = 0;
        System.out.println("建立大根堆第" + c++ + "趟: " + Arrays.toString(nums));
        for (int i = (nums.length - 2) / 2; i >= 0; i--) {
//            System.out.println(nums[i]);
            adjustMaxHeap(nums, i, nums.length);
            System.out.println("建立大根堆第" + c++ + "趟: " + Arrays.toString(nums));
        }
    }

    //调整大根堆
    private static void adjustMaxHeap(int[] nums, int k, int size) {
        int t = nums[k];
        //下标从0开始，左孩子为2*n+1, 右孩子为2*n+2

        for (int i = 2 * k + 1; i < size; i = i * 2 + 1) {
            //找到左右孩子最大值
            if (i < size - 1 && nums[i] < nums[i + 1])
                i++;
            if (t >= nums[i])
                break;
            else {
                nums[k] = nums[i];
                k = i;
            }
        }
        nums[k] = t;
    }

    //归并排序
    public static void mergeSort(int[] nums) {
        mergePartition(nums, 0, nums.length - 1);
    }

    private static void mergePartition(int[] nums, int l, int r) {
        if (l < r) {
            int mid = (l + r) / 2;
            mergePartition(nums, 0, mid);
            mergePartition(nums, mid + 1, r);
            merge(nums, l, mid, r);
        }
    }

    private static void merge(int[] nums, int l, int mid, int r) {
        int[] t = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] > nums[j]) {
                t[k++] = nums[j++];
            } else {
                t[k++] = nums[i++];
            }
        }
        while (i <= mid) t[k++] = nums[i++];
        while (j <= r) t[k++] = nums[j++];
        System.arraycopy(t, 0, nums, l, t.length);
    }

    private static void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{2, 5, 1, 7, 8, 3, 4, 9, 0, 6};
//        Sort.InsertSort(nums);
//        Sort.BInsertSort(nums);
//        Sort.ShellSort(nums);
//        Sort.BubbleSort(nums);
//        Sort.QuickSort(nums);
//        Sort.selectSort(nums);
//        Sort.heapSort(nums);
        Sort.mergeSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
